package P767_重构字符串;

import java.util.*;

/**
 * 767. 重构字符串
 * 给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
 * <p>
 * 若可行，输出任意可行的结果。若不可行，返回空字符串。
 * <p>
 * 示例 1:
 * <p>
 * 输入: S = "aab"
 * 输出: "aba"
 * 示例 2:
 * <p>
 * 输入: S = "aaab"
 * 输出: ""
 * 注意:
 * <p>
 * S 只包含小写字母并且长度在[1, 500]区间内。
 */
public class Solution {
    //思路，排序得到26个字母的重复个数,最多的那个字母比如是X,插入
    //后面的依次从第一个X右侧开始插入，直到X遍历完一次，以后的就从头继续从X的右侧插入
    //从两侧插入即可
    // X   X    X     X    X    X      X      X
    //    a    a    a     a
    //   b(这个b是调转过来的)   b     b    b     b //这一步比较关键 如果b出头了，需要调转回去从X右侧插入
    //  c    c     c
    // d    d
    //只要把x中间的空都填过一遍，剩下的，每次都往X右侧填即可

    public String reorganizeString(String S) {
        Map<Integer, Integer> map = new HashMap<>(26);
        for (char c : S.toCharArray()) {
            map.put((int) c, map.getOrDefault((int) c, 0) + 1);
        }
        List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(map.entrySet());
        entries.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        if (entries.get(0).getValue() > Math.ceil(S.length() / 2.0d)) {
            return "";
        }

        LinkedList<Integer> linkedList = new LinkedList<>();

        Map.Entry<Integer, Integer> firstEntry = entries.remove(0);
        int firstChar = firstEntry.getKey();
        int firstNum = firstEntry.getValue();
        //先放第一个的
        for (int i = 0; i < firstNum; i++) {
            linkedList.add(firstChar);
        }
        boolean firstAllOk = false;
        int curTotalNum = 0; //当前已经填充的数量，需要和firstNum比较，只有curTotalNum >= firstNum - 1的时候才铺满依次
        int size = firstNum;
        int curCharNum,curChar;
        int i =0;
        for(Map.Entry<Integer,Integer> entry : entries){
            curCharNum = entry.getValue();
            curChar = entry.getKey();
            if(firstAllOk){
                //铺满后每次从0开始
                i=0;
            }
            for(; i < size && curCharNum > 0; i++){
                if(linkedList.get(i) == firstChar){
                    curCharNum--;
                    linkedList.add(i + 1, curChar);
                    size ++;
                    if(!firstAllOk && ++curTotalNum >= firstNum){
                        firstAllOk = true;
                        i=0;
                    }

                }
            }
        }


        StringBuilder sb = new StringBuilder();
        for(Integer s : linkedList){
            sb.append((char)(int)s);
        }
        return sb.toString();



    }

    public static void main(String args[]) {
        System.out.println("joibeckslfajeckslfdajkslfdajkslfdajslfdajslfdajslfdajfdajfdajdj".length());
        System.out.println("aabccadfdfasejasjdflkjasdlfjoeijjkdjflsajdflsajdflksjdfljasdlfk".length());
        System.out.println(new P767_重构字符串.Solution().reorganizeString("abbabbaaab"));
//        System.out.println(Math.ceil(0.1d));
    }
}
